Faster Sparse Multivariate Polynomial Interpolation of Straight-Line Programs

摘要

Given a straight-line program whose output is a polynomial function of theinputs, we present a new algorithm to compute a concise representation of thatunknown function. Our algorithm can handle any case where the unknown functionis a multivariate polynomial, with coefficients in an arbitrary finite field,and with a reasonable number of nonzero terms but possibly very large degree.It is competitive with previously known sparse interpolation algorithms thatwork over an arbitrary finite field, and provides an improvement when there area large number of variables.